home *** CD-ROM | disk | FTP | other *** search
Text File | 1996-07-09 | 13.7 KB | 565 lines | [TEXT/R*ch] |
- /*
- 1 July 1996.
- Submission to MacTech Programmer's challenge for July-96.
- Copyright 1996, Ernst Munter, Kanata, ON, Canada.
-
- "Connect IV"
-
- The challenge is to write code for a well-known game that will
- compete against other entries, as well as against the clock.
- The game board consists of an NxM array into which two players
- alternate inserting pieces. Pieces are inserted into the top of
- a column in the vertically oriented board, so that they drop
- into the lowest unoccupied cell of that column. The objective is
- to be the first player to arrange 4 or more pieces into a
- vertical, horizontal, or diagonal line.
-
- Solution
- --------
- My solution is based on an unsophisticated look-ahead scheme.
- We search, depth first, up to a maximum depth, to find the move
- which will give the highest board score. Dummy moves are executed
- alternatingly by the 2 players, in a recursive function.
-
- At each recursion level, the board score accumulated at the
- deeper levels is subtracted from the value of the move
- contemplated at this level.
-
- In a full look-ahead to depth N, and with a board width of
- C columns, we would have C^N moves to examine.
-
- Two techniques are combined to reduce the number of moves to
- be examined:
-
- At each level, the search can stop if a certain threshold
- is exceeded or a winning (losing) position is reached.
- Exceeding the threshold would mean that the calling level
- could not gain a better score, given its best score to
- this point.
-
- In order to be able to stop searching (prune the tree),
- we would like to start with moves which give the better
- scores, i.e. rather than go from left to right across
- the board, we start at the position of the last move and
- go alternatingly left and right of that point. This
- tackles the active area of the board first where it is
- more likely to find the best move.
-
- Data Representation
- -------------------
- The scoring relies entirely on a simple representation of
- the state of the board.
-
- The board is visualized as covered with potential lines
- (horizontal, vertical, diagonal) of 4 adjacent fields.
- Each such line is called a "quad".
-
- A given field is associated with at least 3 (corner fields)
- and at most 16 such quads (in the center of a large board).
-
- Each quad can have a state (empty, owned by player 1, owned
- by player 2, or spoiled). The spoiled state implies this
- quad contains pieces from both players, and can no longer
- be a winning quad.
-
- In addition, a non-empty quad has a value, depending on
- how many player pieces it contains.
-
- I have arbitrarily set these values as follows:
- empty 0
- 1 piece 1
- 2 pieces 16
- 3 pieces 256
- 4 pieces 4096
-
- The value of a placing a piece in a given field, is calculated
- as the sum of the values of all quads associated with this
- field.
-
- To simplify the book keeping, each field has an associated
- data structure which points to all relevant quads.
-
- The Field structure also provides local stack space to hold
- the previous values of its quads while a move is explored.
-
- A recognized weakness of this approach is that it treats
- all quads equally, and does not recognize gravity, that is
- the need to fill columns from the bottom. This effect
- can shadow otherwise good candidates from ever winning.
- I had no time left to include this consideration in the
- board scoring.
-
- Running Time
- ------------
- The depth of the tree dramatically affects the time to
- compute a move, as does the width of the board.
-
- A few minor techniques are used to improve running time.
-
- After each move, all spoiled quads are removed from their
- field references.
-
- All full columns are excluded from the move list.
-
- Empty columns "far away" from the action are also excluded.
-
- The MAGIC_NR constant can be used to adjust the speed
- of the program. A higher value increases the search
- depth and the running time.
-
- I set MAGIC_NR to 17 for acceptable all-round performance
- on my computer.
-
- Assumptions
- -----------
- At least 7 columns are assumed.
- The calling program should check for wins;
- it is assumed that this function is not called
- if the opponent has already won.
-
- A move value of -1 is returned when errors are
- detected, e.g when there are no free fields left.
-
- This program does not include a randomizer since
- it is assumed it will play only a few times against
- computer opponents who, we hope will not be able
- to take advantage of this.
-
- In a version to be played by humans, one would
- randomly choose between equally good moves to
- make it more interesting.
-
- Note on style
- -------------
- This program is basically a C program in spirit,
- but using C++ structs for convenience in accessing
- dynamic data.
-
- No inheritance, operator overloading or the like.
-
- All simple functions are listed inline, as part of the
- class. The implementations of functions with loops
- are listed separately, following the struct declaration.
- */
-
- #include <stdlib.h>
- //#include "viervier.h"
-
- #define maxRow 63
- #define maxCol 64
-
- #define maxQuad (((maxRow-3)*maxCol)+ \
- ((maxCol-3)*maxRow)+(maxRow-3)*(maxCol-3)*2)
- #define empty 0
- #define self 1
- #define opponent 2
- #define spoiled 3
-
- #define OTHER_PLAYER (3-player)
- #define WIN 4096
- #define MAX_MOVES 9
-
- /*** This seems to work for me here, but please adjust
- MAGIC_NR downward if program seems too slow *******/
- #define MAGIC_NR 17
-
- struct Quad {
- short status; //who owns quad
- short value; //16 ^ (n-1);
-
- int Update(int currentPlayer){
- if (status==empty) {
- status=(short)currentPlayer;
- value=1;
- return value;
- }
- if (status==currentPlayer) {
- value <<= 4; //higher value
- return value;
- }
- if (status != spoiled) { //other player
- status=spoiled;
- return value; //plus for us
- }
- return 0; //already spoiled
- }
- };
- typedef struct Quad Quad;
-
- struct Field {
- Quad* quadRef[16]; //pointers to intersecting quads
- Quad savedState[16]; //stack to save quads before move
-
- void AddQuad(Quad* qp);
- void SaveState();
- void RestoreState();
- int MakeMove(int currentPlayer);
- void Rationalize();
- int IsEmpty(){
- if (quadRef[0]->status) return 0;
- return 1;
- }
- };
- typedef struct Field Field;
-
- void Field::AddQuad(Quad* qp) { //adds qp to list of quads
- int k;
- for (k=0;k<16;k++) {
- if (0==quadRef[k]) {
- quadRef[k]=qp;
- break;
- }
- }
- }
-
- void Field::SaveState() { //save all quads on stack
- Quad* qp;
- Quad** qh=quadRef;
- Quad* savePtr=savedState;
- int k;
- for (k=0;k<16;k++) {
- if (0 == (qp=*qh++)) break;
- *savePtr++=*qp;
- }
- }
-
- void Field::RestoreState() { //restore quads from stack
- Quad* qp;
- Quad** qh=quadRef;
- Quad* savePtr=savedState;
- int k;
- for (k=0;k<16;k++) {
- if (0 == (qp=*qh++)) break;
- *qp=*savePtr++;
- }
- }
-
- int Field::MakeMove(int currentPlayer) {
- long sum=0;
- long val;
- Quad* qp;
- Quad** qh=quadRef; //move=update all quads
- //return value of move
- int k;
- for (k=0;k<16;k++) {
- if (0 == (qp=*qh++)) break;
- val=qp->Update(currentPlayer);
- if (val>=WIN) {
- return WIN;
- }
- sum+=val;
- }
- return sum;
- }
-
- void Field::Rationalize() {
- int i=0;
- int k;
- int nq=0; //remove all spoiled quads
-
- //find number of non-0 quad refs
- for (k=0;k<16;k++) {
- if (quadRef[nq]) nq++;
- else break;
- }
-
- //scan quad refs for spoiled quads, and remove
- while(i<nq) {
- Quad* qp=quadRef[i];
- if (qp->status==spoiled) {
- nq--;
- if (i<nq)
- quadRef[i]=quadRef[nq];
- quadRef[nq]=0;
- }
- i++;
- }
- }
-
- struct PrivateData {
- int nextMove; //next real move to do
- int numCols; //number of columns
- int numRows; //number of rows
- int numFree; //number of fields free
- int level; //recursion depth
- int numMoves; //number of moves in move list
- Field* endOfBoard; //sentinel pointer
- int numHistory; //move counter
- int history[maxCol*maxRow];//move history
- int moveList[maxCol]; //list of columns
- Field* nextField[maxCol]; //next free field in column
- Field board[maxCol*maxRow]; //array of all fields
- Quad quadSet[maxQuad]; //array of all quads
-
- void Initialize(long nCols,long nRows);
- void FirstMove() {nextMove = numCols >> 1;}
- void MakeMoveList(int move);
- int BestMove(int level,int player,int threshold);
- void Rationalize(int move);
- int CannedMove();
- void RecordMove(int move) {
- if (numHistory==0)
- history[numHistory++]=move;
- else history[numHistory++]=move-history[0];
- }
- void AdjustLevel() {
- level=MAGIC_NR - numMoves;
- if (numMoves<=7) level--;
- if (level>=numFree) level=numFree-1;
- }
- int UpdateBoard(int move,int player) {
- Field* fp=nextField[move];
- long score=fp->MakeMove(player);
- nextField[move]=fp+numCols;
- Rationalize(move);
- numFree--;
- return score;
- }
- };
- typedef struct PrivateData PrivateData;
-
- /*
- field numbering example (6*7)
-
- 35 36 37 38 39 40 41 5 |
- |
- 28 29 30 31 32 33 34 4
- r
- 21 22 23 24 25 26 27 3 o
- w
- 14 15 16 17 18 19 20 2 s
-
- 7 8 9 10 11 12 13 1 |
- |
- 0 1 2 3 4 5 6 0 |
- -- columns --
- */
- void PrivateData::Initialize(long nCols,long nRows){
- int col,row;
- Field* field;
- Quad* qp;
-
- numCols=nCols;
- numRows=nRows;
- numFree = nCols*nRows;
-
- endOfBoard=board+numFree;
-
- field=board;
- for (col=0;col<nCols;col++)
- nextField[col]=field++;
-
- field=board;
- qp=quadSet;
- for (row=0;row<nRows;row++) { //set up quad references
- for (col=0;col<nCols;col++) {
- int direction,delta;
- for (direction=0;direction<4;direction++) {
- //right, up-right, up, up-left
-
- switch (direction) {
- //eliminate all that dont fit
- case 0: if (col>=nCols-3) continue;break;
- case 1: if (col>=nCols-3) continue;
- case 2: if (row>=nRows-3) continue;break;
- case 3: if ((row>=nRows-3) || (col<3)) continue;
- }
-
- for (delta=0;delta<4;delta++) {
- Field* fp;
- switch (direction) {
- case 0: fp=field+row*nCols+(col+delta);break;
- case 1: fp=field+(row+delta)*nCols+(col+delta);break;
- case 2: fp=field+(row+delta)*nCols+col;break;
- case 3: fp=field+(row+delta)*numCols+(col-delta);break;
- }
- fp->AddQuad(qp);
- }
- qp++;
- }
- }
- }
- }
-
- void PrivateData::Rationalize(int move) {
-
- //remove spoiled quads from all free fields in
- //the vicinity of a recent move
-
- int i=move-3,j=move+4;
- if (i<0) i=0;
- if (j>numCols) j=numCols;
- for (;i<j;i++) {
- Field* fp=nextField[i];
- while (fp<endOfBoard) {
- fp->Rationalize();
- fp+=numCols;
- }
- }
- }
-
- void PrivateData::MakeMoveList(int move) {
- int m=move;
- int n=0;
- int k=0;
-
- //build the move sequence, starting from the center
- //out to the limits while skipping full columns.
-
- do {
- if (nextField[m]<endOfBoard) moveList[n++]=m;
- if (n>=MAX_MOVES) goto done;
- k++;
- if (0>(m=m-k)) goto go_right;
- if (nextField[m]<endOfBoard) moveList[n++]=m;
- if (n>=MAX_MOVES) goto done;
- k++;
- if (numCols<=(m=m+k)) goto go_left;
- } while(1);
-
- go_left:
- if (0>(m=m-k-1)) goto done;
- do {
- if (nextField[m]<endOfBoard) moveList[n++]=m;
- if (n>=MAX_MOVES) goto done;
- m--;
- } while(m>=0);
- goto done;
-
- go_right:
- if (numCols<=(m=m+k+1)) goto done;
- do {
- if (nextField[m]<endOfBoard) moveList[n++]=m;
- if (n>=MAX_MOVES) goto done;
- m++;
- } while(m<numCols);
-
- done:
- numMoves=n;
- }
-
- int PrivateData::CannedMove() {
- #define H0 (history[0])
- switch (numHistory) {
- case 1: if (H0>=3) return H0;
- if (H0+3<numCols) return H0;
- return numCols/2;
- case 2: switch (history[1]) {
- case 0:return H0;
- case 1:if (H0>=3) return H0-3;
- else return H0;
- case -1:if (numCols-H0>3) return H0+3;
- else return H0;
- case 2:case -2:return H0;
- case 3:if (H0>=1) return H0-1;
- else return H0-1;
- case -3:if (numCols-H0>1) return H0+1;
- else return H0+1;
- default:if (H0>=2) return H0-1;
- else return H0+3;
- }
- case 3: if (history[1]==0) {
- if (history[2]>=0) return H0-1;
- if (history[2]<0) {
- if (H0+1<numCols) return H0+1;
- }
- }
- }
- return -1;
- }
-
- int PrivateData::BestMove(int level,int player,int threshold) {
- int i;
- int bestMove=-1;
- int moveValue;
- int score;
- int bestV=-0x4000L;
-
- //this routine is called recursively to return the value
- //of the best move. The class variable "nextMove" holds
- //the column number for the "best" move.
-
- for (i=0;i<numMoves;i++) {
- int m=moveList[i]; //work from list
- Field* fp=nextField[m];
- if (fp < endOfBoard) { //else column is full
- fp->SaveState();
- nextField[m]+=numCols;
- moveValue = fp->MakeMove(player);
-
- if (moveValue>=WIN) { //win here: return right away
- nextField[m]=fp;
- fp->RestoreState();
- nextMove=m;
- return WIN*2;
- }
-
- if (level) { //descend to next level
-
- score=BestMove(level-1,OTHER_PLAYER,moveValue-bestV);
- if (score>=WIN) {
- moveValue=-score+1024;//bias for depth
- goto skip;
- }
- moveValue -= score; //and accumulate score
- }
-
- if (moveValue>=threshold) {
- //no need to search further
- nextField[m]=fp;
- fp->RestoreState();
- nextMove=m;
- return moveValue;
- }
- skip:
- if (moveValue>bestV) { //keep track of best so far
- bestV=moveValue;
- bestMove=m;
- }
-
- nextField[m]=fp;
- fp->RestoreState();
- }
- }
- nextMove=bestMove;
- return bestV;
- }
-
- long ConnectMove4 (
- long numCols,
- long numRows,
- void *privStorage,
- long prevMove,
- Boolean newGame,
- Boolean *victory) {
-
- PrivateData* PD=(PrivateData*)privStorage;
-
- if (newGame) { //initialize on first call
- PD->Initialize(numCols,numRows);
- if (prevMove==-1) {
- PD->FirstMove(); //standard first move
- goto finish;
- }
- }
-
-
- PD->UpdateBoard(prevMove,2);
- PD->RecordMove(prevMove);
-
- if (PD->numFree<=0) return -1; //the board is full
-
- if ((PD->nextMove=PD->CannedMove())<0) {
-
- PD->MakeMoveList(prevMove);
-
- PD->AdjustLevel();
-
- PD->BestMove(PD->level,1,WIN);
- }
- finish:
- *victory=(WIN<=PD->UpdateBoard(PD->nextMove,1));
- PD->RecordMove(PD->nextMove);
- return PD->nextMove;
- }
-